This invention pertains to methods and systems for fingerprinting digital data.
Fingerprinting is a technique that involves uniquely marking each copy of a particular object, and associating each uniquely marked copy with a particular entity to which the copy is distributed. If unauthorized copies of the uniquely marked copy are made, the fingerprint can be traced back to the original entity to which the copy was initially distributed.
As an example, consider a printed map. When a map maker produces a map, they may want to ensure that those individuals to whom the map is distributed do not make unauthorized copies of the map and distribute them to others. One way that the map maker might protect his maps is to introduce a different trivial error, or fingerprint, (e.g. a non-existent street) into each of the copies of the map that are distributed. Each fingerprint is then associated with an individual to whom the map is to be distributed. By associating each different fingerprint with a different individual, if and when unauthorized copies of that individual""s copy are uncovered, they can be traced back to the original individual by virtue of the unique fingerprint that the map contains.
One problem with this type of fingerprinting can arise when two or more individuals collude for the purpose of discovering their fingerprints. That is, when two or more individuals get together and compare their maps, they can, given enough time, ascertain their unique fingerprints by simply looking for the differences between their maps. If they can ascertain their fingerprint, they can alter it and therefore possibly avoid detection.
In contemporary times, particularly with the advent of the Internet and electronic distribution, fingerprinting digital data (e.g. software, documents, music, and video) for purposes of detecting or deterring unauthorized copying has become particularly important. As in the above map example, collusion by different individuals in the digital context can pose challenges to the owners and distributors of such digital data. Although progress has been made in the area of digital fingerprinting, further strides are necessary to increase the breadth of protection that is afforded by digital fingerprinting. For example, in one fingerprinting system (the xe2x80x9cBoneh-Shaw systemxe2x80x9d discussed in more detail below), some protection against collusion is provided, but only when the number of colluders is relatively small. Thus, there is a need to increase the protection that is provided by digital fingerprinting to provide detection of colluders even when the number of colluders is large.
Accordingly, this invention arose out of concerns associated with providing improved methods and systems for fingerprinting digital data.
Methods and systems for fingerprinting digital data are described. In the described embodiment, Direct Sequence Spread Spectrum (DSSS) technology is utilized. Unique fingerprinting words are defined where each includes at least one spread sequence. In the described embodiment, a fingerprinting word comprises a plurality symbols, called xe2x80x9cxcex93 symbols.xe2x80x9d Each xcex93 symbol is composed of 2c-1 blocks, where c represents the number of colluders that are desired to be protected against. Each block contains d spread sequence chips. The fingerprinting words are assigned to a plurality of entities to which protected objects embedded with the fingerprinting words are to be distributed.
To ascertain the identity of an entity that has altered its unique fingerprinting word, the relative weight of each block is computed in accordance with a defined function and blocks whose weights satisfy a predetermined relationship are xe2x80x9cclippedxe2x80x9d to a so-called working range. Each xcex93-symbol of the altered fingerprinting word is then processed to produce a set of one or more xe2x80x9ccolorsxe2x80x9d that might be the subject of a collusion. Each xcex93-symbol in the fingerprinting word for each entity is then evaluated against a corresponding produced set and the entity having the most overall incriminating xe2x80x9ccolorsxe2x80x9d is incriminated.